class Solution {
public:
    int minCost(vector<vector<int>>& costs) {

        int n = costs.size();

        vector<vector<int>> dp(n + 1, vector(4, 0));

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (j == 0)
                {
                    dp[i][j] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][j];
                }
                else if (j == 1)
                {
                    dp[i][j] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][j];
                }
                else if (j == 2)
                {
                    dp[i][j] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][j];
                }
            }
        }

        int ans = min(dp[n][0], dp[n][1]);

        ans = min(ans, dp[n][2]);

        return  ans;
    }
};